1. Field of the Invention
The present invention relates to process checkpointing, and in particular to a method and apparatus for performing hybrid checkpointing.
2. Background Art
Computing environments use a technique known as xe2x80x9ccheckpointingxe2x80x9d which involves saving the state of a program, usually to stable storage, so that it may be reconstructed later in time. Checkpointing is useful for long running computer programs, recovering from a system crash, playback debugging, process migration and job swapping, for example. A checkpoint is like a snapshot in time of the computing environment in which the program is executing. Current problems with checkpointing procedures include latency, the time it takes to store the state of the computing environment on stable storage (such as a disk drive), and the amount of storage space required for the checkpoint.
In some prior art checkpointing the data volume of a checkpoint is roughly proportional to the occupied main memory space of the respective checkpointed process. Due to the volume, such checkpointing operations have an undesirably high latency. Parallelization can improve responsiveness. For instance, UNIX(trademark) based operating system environments provide a xe2x80x9cforkxe2x80x9d command. When a fork instruction is executed, the process concerned splits into a parent and child process. Both the parent and child process continue to execute independently from after the fork intruction. Using such functionality, one can simultaneously checkpoint both the parent and child processes. This type of parallelization, however, does not reduce overall resource consumption.
Internal checkpointing can be used to implement persistent programming languages. Persistent programming languages are languages that are extended to handle persistent data. Persistent data is data that continues to exist even after the process that created it has stopped executing. Existing persistent programming language implementations include: Napier, Tycoon, and PJama, for instance.
Persistent programming languages utilize object caches. Caches are implemented under the assumption that it is very likely that some piece of data will be repeatedly accessed. Access delays are minimized by keeping popular data close to the entity which needs it. Object caches allow for efficient internal checkpointing on a per object basis. Large amounts of memory may be checkpointed with few writes to disk. In addition, persistent programming languages can update the cache automatically. Thus, persistent programming languages implementing object caches produce relatively low data volume per checkpoint and have a short latency. In addition, persistent programming languages implementing object caches can operate when the size of the data exceeds the size of virtual memory.
Persistent programming languages with an external programming interface, however, cannot capture the entire execution state of a program. The internal execution state resides in an object heap. An object heap is an area of memory reserved for objects that are created at runtimexe2x80x94that is, when the program actually executes. Taking the object heap and checkpointing the objects in that heap does not allow one to checkpoint native states, such as execution threads, native functions, or memory allocation regions that are not on the object heap, but reside on other general purpose heaps. Thus, data that is outside the direct control of the given runtime system (native data) is lost. Some native data can be integrated by dedicated explicit programming in the persistent language and external languages, but this is generally not possible.
Native checkpointing records the native state of a process to a secondary storage medium. The native state of a process comprises, for example, memory regions that have been allocated and memory mapped, the contents of those regions, (i.e., copies of the random access memory that contains those regions), active thread stacks, registers for the active threads, and kernel state, such as signal handlers and file handles and other entities that allow the operating system to support the program. Compression reduces the data volume associated with checkpointing by compressing the data that is stored.
When a checkpoint is taken, only the portion of the checkpoint that has changed since the previous checkpoint need to be saved. The unchanged portion can be restored from previous checkpoints. Incremental checkpointing usually may be implemented through the use of page protection hardware to identify the unchanged portion of the checkpoint. Saving only the changed portion reduces the size of each checkpoint, and thus the overhead of checkpointing. Old checkpoint files, however, cannot be deleted when incremental checkpointing is employed, because the program""s data state is spread out over many checkpoint files. Thus, the cumulative size of incremental checkpoint files will increase at a steady rate over time, since many updated values may be saved for the same page.
Native checkpointing in a Java(trademark) environment have been described in connection with the xe2x80x9cicee systemxe2x80x9d. The icee system is based entirely on a paging system implemented by the Solari(trademark) version 2.5.1 operating system. (John Howell, Straightforward Java Persistence Through Checkpointing, in Advances in Persistent Object Systems, Ron Morrison, Mick Jordan, and Malcolm Atkinson, editors, pages 322-334, Morgan Kaufman, 1999. (Presented at the Third International Workshop on Persistence and Java, Sep. 1-3, 1998.) Compression and incremental techniques can take place in an infinite number of computing environments. An example of a Java technology environment where these techniques can be implemented is described below.
A program which utilizes Java technology is composed of a number of classes and interfaces. Unlike many programming languages, in which a program is compiled into machine-dependent, executable program code, programs which utilize Java technology are compiled into machine independent bytecode class files. Each class contains code and data in a platform-independent format called the class file format. The computer system acting as the execution vehicle contains a program called a virtual machine, which is responsible for executing the code in classes. The virtual machine provides a level of abstraction between the machine independence of the bytecode classes and the machine-dependent instruction set of the underlying computer hardware. A xe2x80x9cclass loaderxe2x80x9d within the virtual machine is responsible for loading the bytecode class files as needed, and either an interpreter executes the bytecodes directly, or a xe2x80x9cjust-in-timexe2x80x9d (JIT) compiler transforms the bytecodes into machine code, so that they can be executed by the processor. FIG. 1 is a block diagram illustrating a sample network application environment, for instance a Java network application environment, comprising a client platform 102 coupled over a network 101 to a server 100 for the purpose of accessing class files for execution of an application or applet.
In FIG. 1, server 100 comprises development environment 104 for use in creating the class files for a given application. The development environment 104 provides a mechanism, such as an editor and an applet viewer, for generating class files and previewing applets. A set of core classes 103 comprise a library of classes that can be referenced by source files containing other/new classes. From development environment 104, one or more source files 105 are generated. Source files 105 contain the programmer readable class definitions, including data structures, method implementations and references to other classes. Source files 105 are provided to compiler 106, which compiles source files 105 into compiled xe2x80x9c.classxe2x80x9d files 107 that contain bytecodes executable by a virtual machine. Bytecode class files 107 are stored (e.g., in temporary or permanent storage) on server 100, and are available for download over network 101.
Client platform 102 contains a virtual machine (VM) 111 which, through the use of available native operating system (O/S) calls 112, is able to execute bytecode class files and execute native O/S calls when necessary during execution. Class files are often identified in applet tags within an HTML (hypertext markup language) document. A web server application 108 is executed on server 100 to respond to HTTP (hypertext transport protocol) requests containing URLs (universal resource locators) to HTML documents, also referred to as xe2x80x9cweb pages.xe2x80x9d When a browser application executing on client platform 102 requests an HTML document, such as by forwarding URL 109 to web server 108, the browser automatically initiates the download of the class files 107 identified in the applet tag of the HTML document. Class files 107 are typically downloaded from the server and loaded into virtual machine 111 individually as needed.
It is typical for the classes of a program to be loaded as late during the program""s execution as possible; they are loaded on demand from the network (stored on a server), or from a local file system, when first referenced during the program""s execution. The virtual machine locates and loads each class file, parses the class file format, allocates memory for the class""s various components, and links the class with other already loaded classes. This process makes the code in the class readily executable by the virtual machine.
In a platform independent environment, such as a Java technology environment or other suitable runtime environment, incremental techniques involve taking the underlying pages that form the address space of the program and saving those pages to disk as well as the data which describes the program state. Saving data in this manner creates a representation of what the program was doing at a specific point in time. This technique, in essence, creates a xe2x80x9chard copyxe2x80x9d of the program and has the advantage (unlike persistent programming language techniques) of recording native state (i.e., what the program was doing at an operating system level).
A common incremental technique is to save only the modified virtual memory pages in a checkpoint. By saving only the modified virtual memory pages in a checkpoint, the total volume of a program is restricted to the maximum size of virtual memory, (one to two gigabytes in a 32-bit system, for example). To keep the checkpoint data volume low, such paging requires significant improvements in clustering, which do not currently exist and are not likely to be developed in a general purpose computing environment. Thus, native checkpointing is expensive and has address space limitations, whereas internal checkpointing is incomplete, as it loses native data.
The present invention provides a method and apparatus for hybrid checkpointing. Hybrid checkpointing allows for efficient checkpointing of an internal and a native state of a process. The invention eliminates the disadvantages of the prior art by capturing the entire address space of a process (i.e., both language internal and language external (native) memory and program state).
Initially, the invention halts a currently active process. Next, the invention records the native state of a process, including threads. Next, the invention records the internal state of a process and implements the benefits of persistent object caching. Thereafter, the invention checkpoints the process, and re-starts the process to execution.
In one embodiment, the invention builds and utilizes a catalogue. The catalogue records the native and internal states from prior checkpoints. Upon the invocation of a new checkpoint, the invention accesses the catalogue and determines what states have changed since the last checkpoint. If some of the states have changed the invention updates the catalogue and only checkpoints those changed states, thereby operating with enhanced efficiency. In one embodiment, the invention is configured to checkpoint a process which is executing in a platform independent environment, such as a Java technology environment.